// Go作者版权所有。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

package flate

import "math"

// 这种将速度置于输出大小之上的编码算法是
// 基于Snappy的LZ77样式编码器：github.com/golang/Snappy

const (
	tableBits  = 14             // 表中使用的位。
	tableSize  = 1 << tableBits // 桌子的大小。
	tableMask  = tableSize - 1  // 表索引的掩码。冗余，但可以消除边界检查。
	tableShift = 32 - tableBits // 右移以获取uint32的表位最高有效位。

	// 达到此值时重置缓冲区偏移量。
	// 偏移量作为int32值存储在块之间。
	// 因为我们要检查的偏移量是在开始时
	// 对于缓冲区，我们需要减去电流和输入
	// 缓冲区以避免int32溢出的风险。
	bufferReset = math.MaxInt32 - maxStoreBlockSize*2
)

func load32(b []byte, i int32) uint32 {
	b = b[i : i+4 : len(b)] // 帮助编译器消除下一行的边界检查。
	return uint32(b[0]) | uint32(b[1])<<8 | uint32(b[2])<<16 | uint32(b[3])<<24
}

func load64(b []byte, i int32) uint64 {
	b = b[i : i+8 : len(b)] // 帮助编译器消除下一行的边界检查。
	return uint64(b[0]) | uint64(b[1])<<8 | uint64(b[2])<<16 | uint64(b[3])<<24 |
		uint64(b[4])<<32 | uint64(b[5])<<40 | uint64(b[6])<<48 | uint64(b[7])<<56
}

func hash(u uint32) uint32 {
	return (u * 0x1e35a7bd) >> tableShift
}

// 这些常量由Snappy实现定义，以便
// 程序集实现可以快速路径每次16字节的拷贝。他们
// 在纯Go实现中不需要，因为我们不使用相同的
// 优化，但使用相同的阈值并没有真正的伤害。
const (
	inputMargin            = 16 - 1
	minNonLiteralBlockSize = 1 + 1 + inputMargin
)

type tableEntry struct {
	val    uint32 // 目的地价值
	offset int32
}

// deflateFast维护表中的匹配项，
// 以及用于跨块匹配的前一个字节块。
type deflateFast struct {
	table [tableSize]tableEntry
	prev  []byte // 前一个块，如果未知，则长度为零。
	cur   int32  // 当前匹配偏移量。
}

func newDeflateFast() *deflateFast {
	return &deflateFast{cur: maxStoreBlockSize, prev: make([]byte, 0, maxStoreBlockSize)}
}

// encode对src中给定的块进行编码并附加标记
// 到dst并返回结果。
func (e *deflateFast) encode(dst []token, src []byte) []token {
	// 确保e.cur没有包装。
	if e.cur >= bufferReset {
		e.shiftOffsets()
	}

	// 此检查不在Snappy实现中，但在那里，调用方
	// 而不是被调用方处理此情况。
	if len(src) < minNonLiteralBlockSize {
		e.cur += maxStoreBlockSize
		e.prev = e.prev[:0]
		return emitLiteral(dst, src)
	}

	// sLimit是停止查找偏移/长度副本的时间。输入裕度
	// 让我们在主循环中使用emitLiteral的快速路径，同时
	// 寻找副本。
	sLimit := int32(len(src) - inputMargin)

	// nextEmit是src中下一个emitLiteral的起始位置。
	nextEmit := int32(0)
	s := int32(0)
	cv := load32(src, s)
	nextHash := hash(cv)

	for {
		// 从C++快照实现中复制：
		// None
		// 启发式匹配跳过：如果扫描32个字节时没有匹配项
		// 找到后，开始只查看其他字节。如果再增加32个字节
		// 扫描（或跳过），每三个字节查看一次，等等。。当比赛开始时
		// 找到后，立即返回查看每个字节。这是一个
		// 可压缩数据的小损失（~5%性能，~0.1%密度）
		// 由于簿记较多，但对于不可压缩的数据（如
		// JPEG）这是一个巨大的胜利，因为压缩机很快“实现”了
		// 数据是不可压缩的，不需要费心寻找匹配项
		// 处处
		// None
		// “skip”变量用于跟踪自
		// 最后一场比赛；将其除以32（即右移5）得到
		// 每次迭代要向前移动的字节数。
		skip := int32(32)

		nextS := s
		var candidate tableEntry
		for {
			s = nextS
			bytesBetweenHashLookups := skip >> 5
			nextS = s + bytesBetweenHashLookups
			skip += bytesBetweenHashLookups
			if nextS > sLimit {
				goto emitRemainder
			}
			candidate = e.table[nextHash&tableMask]
			now := load32(src, nextS)
			e.table[nextHash&tableMask] = tableEntry{offset: s + e.cur, val: cv}
			nextHash = hash(now)

			offset := s - (candidate.offset - e.cur)
			if offset > maxMatchOffset || cv != candidate.val {
				// 超出范围或不匹配。
				cv = now
				continue
			}
			break
		}

		// 已找到一个4字节的匹配项。稍后我们将查看是否超过4个字节
		// 火柴但是，在匹配之前，src[nextEmit:s]是不匹配的。发出
		// 将它们作为文本字节。
		dst = emitLiteral(dst, src[nextEmit:s])

		// 打电话给emitCopy，然后看看下一个emitCopy是否可以
		// 移动重复此操作，直到我们在之后立即发现输入不匹配为止
		// 上次emitCopy调用使用的内容。
		// None
		// 如果我们正常退出这个循环，那么我们需要调用emitLiteral next，
		// 虽然我们还不知道文字会有多大。我们会处理的
		// 继续主循环的下一次迭代。我们也可以
		// 如果我们接近耗尽输入，通过goto退出这个循环。
		for {
			// 不变量：我们在s处有一个4字节的匹配，不需要发出任何
			// s之前的文本字节。

			// 尽可能长地扩展4字节匹配。
			// None
			s += 4
			t := candidate.offset - e.cur + 4
			l := e.matchLen(s, t, src)

			// matchToken相当于flate的Snappy的emitCopy。（长度、偏移）
			dst = append(dst, matchToken(uint32(l+4-baseMatchLength), uint32(s-t-baseMatchOffset)))
			s += l
			nextEmit = s
			if s >= sLimit {
				goto emitRemainder
			}

			// 我们现在可以立即在s开始工作，但需要改进
			// 压缩我们首先在s-1和s处更新哈希表。如果
			// 另一个副本不是我们的下一步，也算下一步
			// 在s+1。至少在GOARCH=amd64上，这三个散列计算
			// 一次load64呼叫（有一些班次）比
			// 三个32个电话。
			x := load64(src, s-1)
			prevHash := hash(uint32(x))
			e.table[prevHash&tableMask] = tableEntry{offset: e.cur + s - 1, val: uint32(x)}
			x >>= 8
			currHash := hash(uint32(x))
			candidate = e.table[currHash&tableMask]
			e.table[currHash&tableMask] = tableEntry{offset: e.cur + s, val: uint32(x)}

			offset := s - (candidate.offset - e.cur)
			if offset > maxMatchOffset || uint32(x) != candidate.val {
				cv = uint32(x >> 8)
				nextHash = hash(cv)
				s++
				break
			}
		}
	}

emitRemainder:
	if int(nextEmit) < len(src) {
		dst = emitLiteral(dst, src[nextEmit:])
	}
	e.cur += int32(len(src))
	e.prev = e.prev[:len(src)]
	copy(e.prev, src)
	return dst
}

func emitLiteral(dst []token, lit []byte) []token {
	for _, v := range lit {
		dst = append(dst, literalToken(uint32(v)))
	}
	return dst
}

// matchLen返回src[s:]和src[t:]之间的匹配长度。
// t可以为负值，表示比赛开始于e.prev。
// 我们假设src[s-4:s]和src[t-4:t]已经匹配。
func (e *deflateFast) matchLen(s, t int32, src []byte) int32 {
	s1 := int(s) + maxMatchLength - 4
	if s1 > len(src) {
		s1 = len(src)
	}

	// 如果我们在当前区块内
	if t >= 0 {
		b := src[t:]
		a := src[s:s1]
		b = b[:len(a)]
		// 尽可能延长比赛时间。
		for i := range a {
			if a[i] != b[i] {
				return int32(i)
			}
		}
		return int32(len(a))
	}

	// 我们在上一个区块中找到了匹配项。
	tp := int32(len(e.prev)) + t
	if tp < 0 {
		return 0
	}

	// 尽可能延长比赛时间。
	a := src[s:s1]
	b := e.prev[tp:]
	if len(b) > len(a) {
		b = b[:len(a)]
	}
	a = a[:len(b)]
	for i := range b {
		if a[i] != b[i] {
			return int32(i)
		}
	}

	// 如果我们达到了极限，我们就符合我们的一切
	// 允许我们在上一个街区返回。
	n := int32(len(b))
	if int(s+n) == s1 {
		return n
	}

	// 继续在当前块中查找更多匹配项。
	a = src[s+n : s1]
	b = src[:len(a)]
	for i := range a {
		if a[i] != b[i] {
			return int32(i) + n
		}
	}
	return int32(len(a)) + n
}

// 重置重置编码历史记录。
// 这样可以确保不与上一个块进行匹配。
func (e *deflateFast) reset() {
	e.prev = e.prev[:0]
	// 碰撞偏移，因此所有匹配都将无法通过距离检查。
	// 表中的任何内容都不应大于等于e.cur。
	e.cur += maxMatchOffset

	// 防止e.cur缠绕。
	if e.cur >= bufferReset {
		e.shiftOffsets()
	}
}

// shiftofset将向下移动所有匹配偏移。
// 仅在极少数情况下调用此函数以防止整数溢出。
// None
// 请参阅https:
func (e *deflateFast) shiftOffsets() {
	if len(e.prev) == 0 {
		// 我们没有历史；清理桌子就行了。
		for i := range e.table[:] {
			e.table[i] = tableEntry{}
		}
		e.cur = maxMatchOffset + 1
		return
	}

	// 把桌上所有不太远的东西移下来。
	for i := range e.table[:] {
		v := e.table[i].offset - e.cur + maxMatchOffset + 1
		if v < 0 {
			// 我们想将e.cur重置为maxMatchOffset+1，因此需要移位
			// 所有表项向下移动（e.cur-（maxMatchOffset+1））。
			// 因为我们忽略了matches>maxMatchOffset，所以我们可以
			// 0处的任何负偏移。
			v = 0
		}
		e.table[i].offset = v
	}
	e.cur = maxMatchOffset + 1
}
